/*
* 图结构的基本概念：
*   一个图G = （V，E）由以下元素组成
*       V：一组顶点
*       E：一组边，连接V中的顶点
*
*   1.由一条边连接在一起的顶点称为相邻顶点。比如，A连接B，A连接C，A连接D，B连接E。则A和B相邻，A和C相邻，A和D相邻，A和E不相邻，B和E才相邻。
*   2.一个顶点的度是其相邻顶点的数量。比如，A和其他三个顶点相连接，因此A的度为3。B和两个顶点相连接，B的度为2。
*   3.路径是顶点V1,V2,V3,V4...的一个连续序列，其中Vi和Vi+1是相邻的，比如路径A，B，E，I和路径A，C，D，G
*   4.简单路径要求不包含重复的顶点。例如，A，D，G是一条简单路径。环也是一个简单路径，比如A，D，C，A（最后一个顶点重新回到A）
*   5.如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是连通的。
*
* 图可以是有方向的，也可以是无方向的。如果图中两个顶点间在双向上都存在路径，则该图是强连通的。如C可以到D，D也可以到C，则C和D是强连通的。
*
* 邻接矩阵：每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点与顶点之间的连接。如果索引为i的节点和索引为j的节点相邻，
*         则arr[i][j] === 1，否则arr[i][j] === 0。
* 邻接矩阵的缺点：如果不是强连通的图（稀疏图）用邻接矩阵来表示，则矩阵中会有很多0，意味着浪费了计算机存储空间来表示根本不存在的边。（空间换时间）
*
* 邻接表：邻接表由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。数组列表、链表、散列表或是字典都能用来表示邻接表。
*
* 关联矩阵：矩阵中行表示顶点，列表示边。使用二维数组来表示两者之间的连通性，如果顶点v是边e的入射点，则arr[v][e] === 1，否则arr[v][e] === 0。
*         关联矩阵常用于边的数量比顶点多的情况
*
*
* */

//在字典的基础上实现图结构中的邻接表

class ValuePair{ //存储原始值
    constructor(key,value) { //单个的字典值的节点
        this.key = key
        this.value = value
    }
    toString(){
        return `[${this.key}:${this.value}]` //单个值节点转成字符串
    }
}

class Dictionary{
    constructor(){
        this.table = {} //这个对象就是存储数据的内存空间，key就是内存地址，value就是里面的值
    }
    toStringFN(item){ //形参item就等同于key意思
        if(item === null){ //如果传入的key是null
            return ""
        }else if(item === undefined){ //如果传入的是undefined
            return "Undefined"
        }else if(typeof item === "string" || item instanceof String){ //如果传入的是与字符串有关的
            return `${item}`
        }
        //如果以上情况都不是
        return item.toString()
    }
    hasKey(key){ //判断是否已经在对象中存储了这个值
        return this.table[this.toStringFN(key)] !== undefined
        //因为我们访问的是 已经存在的对象 的key，访问对象的属性，如果返回的不是undefined，则表示存在，返回undefined则表示不存在
    }
    set(key,value){ //往字典里面存储值
        //先判断是否存在
        if(key != null && value != null){
            let tablekey = this.toStringFN(key) //得到一个key
            this.table[tablekey] = new ValuePair(key,value) //存储值
        }
        return false //如果为空返回false
    }
    remove(key){ //删除字典里的某个key所指向的值
        //删除一个值前提是得有这个值
        if(this.hasKey(key)){
            delete this.table[this.toStringFN(key)] //如果有这个值则删除
        }
        return false //没有则返回false
    }
    get(key){ //根据传入的key获取对应的值
        return this.table[this.toStringFN(key)]
    }
    keyValues(){ //获取所有名值对
        let ValuePairs = []
        for(let k in this.table){
            if(this.hasKey(key)){
                ValuePairs.push(this.table[k])
            }
        }
        return ValuePairs
    }
    keys(){ //获取所有名值对的key名
        return this.keyValues().map(item => item.key)
    }
    values(){ //获取所有名值对的value值
        return this.keyValues().map(item => item.value)
    }
    forEach(cb){ //遍历，接收一个回调函数
        let valuePairs = this.keyValues()
        for(let index = 0; index < valuePairs.length; index++){
            cb(index,valuePairs[index].value,valuePairs) //index item arr 这里我改了第二个valuePairs[index].value
        }
    }
    size(){ //获取长度
        return this.keyValues().length
    }
    clear(){ //清空
        this.table = {}
    }
    isEmpty(){ //是否为空
        return this.size() === 0 //如果长度为0则表示是空
    }
    toString(){
        if(this.isEmpty()){
            return ""
        }
        let valuePairs = this.keyValues()
        let objStr = ""
        for(let i = 0; i < valuePairs.length; i++){
            objStr = `${objStr},${valuePairs[i].toStringFN()}` //这里我改了最后的toStringFN
        }
        return objStr.slice(1) //去掉前面的逗号
    }
}

class Graph{ //图
    constructor(isDirected = false) {
        this.isDirected = isDirected //是否为有方向图
        this.vertices = [] //存储顶点的列表
        this.adjList = new Dictionary() //用一个字典结构来存储邻接表，即adjList是用来存储vertices的，vertices是用来存储点与点之间的关系的
    }

    //先添加点，再添加边，没有点哪来的边
    addVertex(v){ //添加点
        if(!this.vertices.includes(v)){ //如果列表中没有该点，才添加该点
            this.vertices.push(v) //顶点列表中添加该点
            this.adjList.set(v,[])
        }
    }

    addEdge(v,w){ //添加边，用两个点模拟形成一条边
        if(!this.adjList.get(v)){ //如果该点不存在则添加该点
            this.addVertex(v)
        }
        if(!this.adjList.get(w)){ //如果该点不存在则添加该点
            this.addVertex(w)
        }
        //此时这两个点没有关系，需要添加关系
        this.adjList.get(v).value.push(w) //将点w添加到点v的邻接表中
        if(!this.isDirected){ //如果是无方向图，则两个点都是互通的
            this.adjList.get(w).value.push(v) //将点v添加到点w的邻接表中
        }
    }

    getVertices(){ //获取所有顶点
        return this.vertices
    }

    getAdjList(){ //获取所有的边
        return this.adjList
    }

    toString(){
        let s = "\n" //在空字符串中价格换行，更好看更对称，其实s就是一个空袋子，先在内存中进行运算，最后再一起集中的，更节省性能
        for(let i = 0; i < this.vertices.length; i++){
            console.log("this.vertices[i]是："+this.vertices[i])
            s += `${this.vertices[i]} -> `
            let neighbors = this.adjList.get(this.vertices[i]).value
            console.log("neighbors是："+neighbors)
            for(let j = 0; j < neighbors.length; j++){
                console.log("neighbors[j]是："+neighbors[j])
                s += `${neighbors[j]},`
            }
            s = s.slice(0,s.length-1)
            s += `\n` //加个换行符更好看
        }
        return s
    }
}

let graph = new Graph()
graph.addEdge("A","B")
graph.addEdge("A","C")
graph.addEdge("A","D")
graph.addEdge("B","E")
graph.addEdge("B","F")
graph.addEdge("C","G")
graph.addEdge("C","D")
graph.addEdge("D","G")
graph.addEdge("D","H")
graph.addEdge("E","I")